/* 
为了支持添加单词和搜索包含通配符 . 的单词，我们可以使用前缀树（Trie）结构，
并在搜索时处理通配符的情况。当遇到 . 时，需要递归检查所有可能的子节点。

方法思路
前缀树结构：每个节点包含子节点映射和是否为单词结尾的标记。
添加单词：与普通前缀树相同，遍历每个字符，创建对应子节点，最后标记单词结尾。
搜索单词：
若字符为 .，递归检查所有子节点。
若字符为普通字母，检查对应子节点是否存在。
递归过程中若匹配失败或到达单词末尾，返回相应结果。
*/
var WordDictionary = function () {
  // 初始化前缀树的根节点
  this.root = new TrieNode();
};

// 前缀树的节点结构
class TrieNode {
  constructor() {
    // 使用普通对象存储子节点，键为字符，值为子节点
    this.children = {};
    // 标记该节点是否为一个单词的结尾
    this.isEnd = false;
  }
}

/** 
 * @param {string} word
 * @return {void}
 */
WordDictionary.prototype.addWord = function (word) {
  let current = this.root;
  // 遍历单词的每个字符
  for (const char of word) {
    // 如果当前字符不在子节点中，创建新的子节点
    if (!(char in current.children)) {
      current.children[char] = new TrieNode();
    }
    // 移动到下一个节点
    current = current.children[char];
  }
  // 标记最后一个字符的节点为单词结尾
  current.isEnd = true;
};

/** 
 * @param {string} word
 * @return {boolean}
 */
WordDictionary.prototype.search = function (word) {
  // 从根节点开始深度优先搜索
  return this.dfs(word, 0, this.root);
};

/**
 * 递归搜索单词的辅助函数
 * @param {string} word - 要搜索的单词
 * @param {number} index - 当前处理的字符索引
 * @param {TrieNode} node - 当前节点
 * @return {boolean} 是否找到匹配的单词
 */
WordDictionary.prototype.dfs = function (word, index, node) {
  // 如果已经处理完所有字符，检查当前节点是否为单词结尾
  if (index === word.length) {
    return node.isEnd;
  }

  const char = word[index];
  // 处理通配符 '.'，需要尝试所有可能的子节点
  if (char === '.') {
    for (const key in node.children) {
      if (this.dfs(word, index + 1, node.children[key])) {
        return true; // 只要有一个路径匹配成功，返回true
      }
    }
    return false; // 所有路径都失败，返回false
  } else {
    // 处理普通字符，检查是否存在对应的子节点
    if (!(char in node.children)) {
      return false;
    }
    // 继续在对应的子节点中搜索下一个字符
    return this.dfs(word, index + 1, node.children[char]);
  }
};